package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/27.<br><br>
 *
 * 中等：不同路径 II
 */
public class Topic63 {
    public static void main(String[] args) {
        Topic63 instance = new Topic63();

        int[][] grid = new int[][] {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(instance.uniquePathsWithObstacles(grid));

        grid = new int[][] {{0,1},{0,0}};
        System.out.println(instance.uniquePathsWithObstacles(grid));
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[] count = new int[col];
        count[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(obstacleGrid[i][j] == 1) {
                    count[j] = 0;
                    continue;
                }
                else if(j > 0 && obstacleGrid[i][j - 1] == 0) {
                    count[j] += count[j - 1];
                }
            }
        }

        return count[col - 1];
    }

    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] count = new int[row][col];
        for(int i = 0; i < row; i++) {
            count[i][0] = obstacleGrid[i][0] == 1 ? 0 : 1;

            if(i > 0 && count[i - 1][0] == 0) {
                count[i][0] = 0;
            }
        }

        for(int j = 0; j < col; j++) {
            count[0][j] = obstacleGrid[0][j] == 1 ? 0 : 1;

            if(j > 0 && count[0][j - 1] == 0) {
                count[0][j] = 0;
            }
        }

        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                if(obstacleGrid[i][j] == 1) {
                    count[i][j] = 0;
                }
                else {
                    count[i][j] = count[i - 1][j] + count[i][j - 1];
                }
            }
        }

        return count[row - 1][col - 1];
    }
}
